package 剑指offer.树;

/**
 * 普通二叉树的几个经典问题
 */
public class 第55题二叉树的深度 {


    public class TreeNode {
        int val = 0;
        TreeNode left = null;
        TreeNode right = null;

        public TreeNode(int val) {
            this.val = val;

        }
    }


    /**
     * 题目一：二叉树的深度
     * 输入一棵二叉树，求该树的深度。
     * 从根结点到叶结点依次经过的结点（含根、叶结点）形成树的一条路径，最长路径的长度为树的深度。
     *
     * 分析思路：若只有根节点，深度就是1
     *          若还有一个左、右子节点，深度就应该是左右子节点的深度得最大值 + 1
     */
    public int TreeDepth(TreeNode root) {
        if (root == null)
            return 0;
        int left = TreeDepth(root.left);
        int right = TreeDepth(root.right);
        return left > right ? left + 1 : right + 1;
    }

    /**
     * 判断一棵树是不是平衡二叉树
     * 平衡二叉树的特点就是任意一个节点的左右子树高度之差不大于1
     */
    public boolean IsBalanced_Solution(TreeNode root) {
        if (root == null)
            return true;
        int left = TreeDepth(root.left);
        int right = TreeDepth(root.right);
        int diff = left - right;
        if (diff > 1 || diff < -1)
            return false;
        // 分别判断每一个节点是否为平衡的
        return IsBalanced_Solution(root.left) && IsBalanced_Solution(root.right);
    }
}
